//
// Created by francklinson on 2021/7/9.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution { // 题解 dfs 拓扑排序
private:
    vector<vector<int>> edges; //邻接表
    vector<int> visited; // 访问记录  0 未搜索 1搜索中 2搜索完成
    bool valid = true;

public:
    /**
     * 我们将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v：
       如果 v 为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u；
       如果 v 为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；
       如果 v 为「已完成」，那么说明 v 已经在栈中了，而 u 还不在栈中，
       因此 u 无论何时入栈都不会影响到 (u,v) 之前的拓扑关系，以及不用进行任何操作。
     * @param u
     */
    void dfs(int u) {
        visited[u] = 1; // 搜索中
        for (int v: edges[u]) { // 遍历该课程的所有先修课
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) { // 正在搜索的课程
                valid = false;
                return;
            }
        }
        visited[u] = 2; // 搜索完成
    }

    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto &info: prerequisites) {
            edges[info[1]].push_back(info[0]); // 每门课程的先导课程 构造邻接表
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) { // 没访问过
                dfs(i);
            }
        }
        return valid;
    }
};

class Solution2 { // bfs  正向
private:
    vector<vector<int>> edges;
    vector<int> indeg;

public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        edges.resize(numCourses);
        indeg.resize(numCourses);
        for (const auto &info: prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];
        }

        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.push(i);
            }
        }

        int visited = 0;
        while (!q.empty()) {
            ++visited;
            int u = q.front();
            q.pop();
            for (int v: edges[u]) {
                --indeg[v];
                if (indeg[v] == 0) {
                    q.push(v);
                }
            }
        }

        return visited == numCourses;
    }
};


int main() {
    vector<vector<int>> prerequisites{{1, 0},
                                      {0, 1},
                                      {2, 3},
                                      {3, 0}};
    Solution solution;
    cout << solution.canFinish(4, prerequisites) << endl;
    return 0;
}